/*
day272
2020.5.26
*/
#include<stack>
#include<cstdlib>
using namespace std;

 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class BSTIterator {
public:
	stack<TreeNode *> sta;
	TreeNode *cur;
	
    BSTIterator(TreeNode* root) {
    	cur=root;
    }
    
    /** @return the next smallest number */
    int next() {
		while(cur)
		{
			sta.push(cur);
			cur=cur->left;
		}
		cur=sta.top();
		sta.pop();
		int res=cur->val;
		cur=cur->right;
		return res;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
		return !(sta.empty() && !cur);
    }
};

int main()
{
	return 0;
}
